1. Field of the Invention
This invention relates generally to the fields of data compression and error correction. In particular, this invention relates to a device which utilizes data compression to free up bandwidth to be used for error correction.
2. Background
Error correction is commonly used in various devices and systems by appending a fixed number of Forward Error Correction (FEC) bits to a fixed number of data bits to allow for correction of a certain number of bit errors. Several methods of performing `fixed` error correction are known in the art. In general, these methods generate a fixed number of error correction bits for each block of fixed length processed.
U.S. Pat. No. 3,506,961 to Abramson et al. describes an adaptive error correction system in which the number of burst errors are examined to determine what level of error correction is required to accomplish a fully correctable transmission. Then an error correction parameter is adjusted to manipulate the block size in accordance with the requirements of the channel. This patent also includes a rather extensive discussion of the background problems with error correction.
U.S. Pat. No. 4,047,151 to Rydbeck et al describes a technique for providing adaptive error correction in digital transmission of analog signals (e.g. voice or video) in which bits of lower significance are sacrificed to provide bandwidth for insertion of error correction bits. However, this arrangement is obviously unsuitable for transmission of digital information since it would actually produce errors which are uncorrectable.
Adaptive error control is also discussed in U.S. Pat. No. 3,496,549 to Tong in which one of several different error control mechanisms is selected based upon the error performance of the channel. For example, burst errors and random errors may be best handled by different error control strategies. This patent allows for tayloring the error correction scheme to best correct for the type of errors produced by the channel.
Several types of data compression are well known in the art. For example, Huffman coding and modifications thereof as described in U.S. Pat. No. 4,700,175 to Robert E. Bledsoe and assigned to the assignee of the present invention, have been used to provide data compression. Other data compression (or compaction) techniques are disclosed in, for example, U.S. Pat. Nos. 3,237,170 to Blasbalg et al, 4,560,976 to Finn, 4,612,532 to Bacon et al, and 4,706,265 to Furukawa. These patents are incorporated herein by reference.
In data compression environments, a constant data input rate is converted into a variable output data rate which is usually considerably lower on average than the input data rate. Thus, data compression typically provides the ability to transmit data using a lower bandwidth than would otherwise be required. Usually this decrease in required bandwidth is used to enhance throughput. That is, any bandwidth freed up by use of data compression is utilized to transport more data thus increasing the effective communication rate. This principal has been utilized, for example, in statistical multiplexers in order to pump more user data through a given link. It has also been utilized with data compressing asynchronous modems so that the modems may be rated at a higher information throughput than the communication channel and modem technology would normally allow.
Unfortunately, the advantage offered by data compression is difficult to utilize with synchronous communications links. Such links require the addition of a substantial level of flow control in order to utilize the variable rate output of a data compressor. A good example of this environment is that of a communication link using synchronous modems. The required flow control adds substantial complexity to the modem thereby substantially increasing its cost.
The present invention utilizes the increase in available bandwidth created by data compression advantageously to indirectly increase the data throughput by increasing the immunity of the data to noise, line disturbances, etc. By enhancing the integrity of the transmitted data, there is a lower need for retransmissions, etc. since many errors can be corrected without use of additional bandwidth.